Not Applicable
All of the material in this patent document is subject to copyright protection under the copyright laws of the United States and of other countries. The owner of the copyright rights has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the United States Patent and Trademark Office file or records, but otherwise reserves all copyright rights whatsoever.
The following publications which are referenced using a reference number inside square brackets (e.g., [1]) are incorporated herein by reference.
[1] D. L. Donoho and I. M. Johnstone, xe2x80x9cIdeal De-Noising in a Basis Chosen from a Library of Orthogonal Bases,xe2x80x9d Comptes Rendus Acad. Sci. Paris A, 319, (1994), pp. 1317-1322.
[2] Edward R. Dougherty, xe2x80x9cAn Introduction to Morphological Image Processing,xe2x80x9d Tutorial Texts in Optical Engineering, vol. TT9, SPIE Optical Engineering Press, Bellingham, Wash. 1991.
[3] E. Abreu, M. Lightstone, S. K. Mitra and K. Arakawa, xe2x80x9cA new Efficient Approach for the Removal of Impulse Noise from highly Corrupted Images,xe2x80x9d IEEE Trans. on Image Processing, vol. 5 (1996), pp. 1012-1025.
[4] Mary Oman, xe2x80x9cStudy of Variational Methods Applied to Noisy Step Data,xe2x80x9d unpublished, 1996.
[5] James M. Ortega, xe2x80x9cMatrix Theory A Second Course,xe2x80x9d Plenum Press, New York, 1987.
[6] S. Osher and L. Rudin, xe2x80x9cFeature-Oriented Image Enhancement Using Shock Filters,xe2x80x9d SIAM J. Numer. Anal., vol. 27, pp. 919-940, 1990.
[7] S. Osher and L. Rudin, xe2x80x9cShocks and Other Nonlinear Filtering Applied to Image Processing,xe2x80x9d Proceedings SPIE Appl. Dig. Image Proc. XIV, vol. 1567, pp. 414-430, 1991.
[8] L. Rudin, xe2x80x9cImages, Numerical Analysis of Singularities, and Shock Filters,xe2x80x9d Ph.D. thesis, Computer Science Dept., Caltech, Pasadena, Calif., Tech. Report 5250:TR:87, 1987.
[9] L. P. Yaroslavsky, xe2x80x9cLinear and Rank Adaptive Filters for Picture Processing,xe2x80x9d in Digital Image Processing and Computer Graphics: Theory and Applications, L. Dimitrov and E. Wenger, Eds. Wien, Muenchen: R. Oldenburg, pp. 374, 1991.
[10] L. Yin, R. Yang, M. Gabbouj and Y. Neuvo, xe2x80x9cWeighted Median Filters: A Tutorial,xe2x80x9d IEEE Trans. Circ. Sys. -II: Analog and Dig. Sig. Proc., vol. 43 (1996) pp. 157-192.
1. Field of the Invention
This invention pertains generally to image processing, and more particularly to a fast image processing method that selectively segments and enhances objects of a given diameter and area.
2. Description of the Background Art
In most computer vision applications, image enhancement and image segmentation constitutes a crucial initial step before performing high-level tasks such as object recognition and scene interpretation. However, despite considerable research and progress made in this area, the robustness and generality of the algorithms on large image datasets have not been established. Furthermore, image segmentation itself is an ill-posed problem. It requires additional information from the user in order to select a proper scale for detecting the useful edges or boundaries, and thus, segmenting the objects or detecting the useful edges or boundaries, and thus, segmenting the objects or regions of interest.
The present invention generally comprises two steps to enhance objects with n or more pixels: (a) identify a peer group of size n for each pixel; and (b) process the pixel value based on the characteristics of the peer group. More particularly, the invention comprises a method that identifies, at each pixel in an image, a nearby group (peer group) of similar pixels. Using a window diameter d and a peer group number n, the peer group for a pixel is selected from the window centered at the pixel and consists of the n pixels whose values are closest to the center value. For example, the pixel similarity criteria for assignment to a peer group might be intensity nearness. Once the peer group is identified, the values are averaged to obtain a new pixel value for the center pixel. This method eliminates noise spikes and gives a piecewise constant approximation of the original image.
There are many ways to select the peer group for a given pixel. For example, see the earlier work by Yaroslavsky [9] presenting an abstract formulation of the group idea. In general, peer group members should share common values. For a single image, the peer group may be nearby pixels with similar intensity values. For a sequence of images used in determining optical flow fields, the peer group can be nearby pixels (in time and space) with similar intensity values and similar velocity values. In another context, texture values may be assigned to each pixel and then the peer group determined by nearness in texture space.
By way of example, and not of limitation, the present invention is directed to peer group averaging (PGA) for peer groups based on intensity nearness. For a given image g, we select a window diameter d and a peer group number n. The selection of d and n should correspond to the size of the objects that are to be enhanced and segmented. The peer group for a pixel is selected from the window centered at the pixel and comprises the n pixels whose intensity values are closest to the center value. For example, let u be the average over the peer group. If we let Ak be the averaging operator at step k we can represent the PGA iteration as uk+1=Akuk where u0=g.
The PGA iteration is nonlinear because of the peer group selection. During the first few iterations the peer groups can change membership significantly. After this transition phase the peer groups remain rather static. This suggests fixing the peer groups after a certain number of iterations (say for kxe2x89xa7k0). The PGA iteration then has the form uk+1=Auk for kxe2x89xa7k0 where A is independent of k. This linear iteration is fast (since the peer group selection is not done at each step) and can be analyzed (See Theorem 2 below).
Convergence of the PGA iteration for one dimensional (1d) signals and images is discussed in Section 1 below, followed by a discussion of how to achieve efficiency for large window sizes. The main result discussed in that section is that the PGA algorithm converges to an image that is constant on the interior regions of the image (the xe2x80x9cirreduciblexe2x80x9d subsets discussed in Theorem 2 below). Section 1 concludes with a discussion of the connection between PGA and shock filtering methods.
In Section 2 below, we also address the problem of parameter selection for PGA. The first part of Section 2 discusses some empirical observations and supporting examples. This is followed by analytical results on the interplay between window diameter, peer group number and the object of interest.
Lastly, in Section 3 we briefly discusses an application to size related filtering.
An object of the invention is to provide an image processing method with edge preservation and enhancement.
Another object of the invention is to provide an image processing method that exhibits computational speed and ease of implementation, especially in comparison to more computationally intensive methods such as PDE based segmentation schemes.
Another object of the invention is to provide an image processing method that allows may analytical results to be obtained concerning the convergence of the PGA iteration, relations to other methods such as shock filtering and median filtering, and how the choice of parameters affects the resulting approximation.
Another object of the invention is to provide an image processing method directly related to the characteristics of the image objects that are to be enhanced.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.